package com.dzu.medium;

import java.util.*;

/**
 * @author ZhaoDong
 * @date 2022/10/9 9:54
 * @description 49. 字母异位词分组
 */
public class Test49 {

    public static void main(String[] args) {
        String[] str = new String[]{"", ""};
        System.out.println(groupAnagrams2(str));
    }

    // 官方 6ms
    public static List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key, list);
        }

        return new ArrayList<>(map.values());


    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> resp = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            Integer temp = map.get(str);
            if (temp != null) {
                continue;
            }
            List<String> list = new ArrayList<>();

            resp.add(list);
            list.add(str);

            map.put(str, map.getOrDefault(str, 0) + 1);

            for (int i1 = i + 1; i1 < strs.length; i1++) {
                String s = strs[i1];
                if (str.length() != s.length()) {
                    continue;
                }
                int[] arr = new int[26];
                for (int j = 0; j < str.length(); j++) {

                    arr[str.charAt(j) - 'a']++;
                    arr[s.charAt(j) - 'a']--;
                }
                boolean flag = false;
                for (int i2 : arr) {
                    if (i2 != 0) {
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    list.add(s);
                    map.put(s, map.getOrDefault(s, 0) + 1);
                }
            }
        }

        return resp;
    }
}
